public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "ADOBECODEBANC";
        String t = "ABC";
        System.out.println(solution.minWindow(s, t));
    }
}
class Solution {
    public String minWindow(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();
        int[] hash1 = new int[128];
        int[] hash2 = new int[128];
        int kinds = 0;
        for (char ch:t) {
            if (hash1[ch]++==0) kinds++;
        }
        int begin = -1,minlen = Integer.MAX_VALUE;
        for (int left=0,right=0,count=0;right<s.length;right++) {
            //进窗口
            char in = s[right];
            hash2[in]++;
            if (hash2[in]==hash1[in]) count++;
            //更新结果
            while (count==kinds) {
                if (right-left+1<minlen) {
                    begin = left;
                    minlen = right-left+1;
                }
                //出窗口
                char out = s[left];
                if (hash2[out]==hash1[out]) count--;
                hash2[out]--;
                left++;
            }

        }
        if (begin==-1) return new String();
        return ss.substring(begin,begin+minlen);
    }
}